from functools import cache
from typing import *
from heapq import heappop, heappush


class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        m, n = len(grid), len(grid[0])
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        h = [[0] * n for _ in range(m)]
        h[0][0] = health - grid[0][0]
        q = [(-h[0][0], 0, 0)]
        while q:
            hth, x, y = heappop(q)
            if x == m - 1 and y == n - 1:
                return hth < 0
            for a, b in d:
                if (
                    (nx := x + a) >= 0
                    and nx < m
                    and (ny := y + b) >= 0
                    and ny < n
                    and (nhth := -hth - grid[nx][ny]) > h[nx][ny]
                ):
                    h[nx][ny] = nhth
                    heappush(q, (-nhth, nx, ny))

        return False


so = Solution()
print(
    so.findSafeWalk(grid=[[0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0]], health=1)
)
